/********************************************************************************
* @Author: Zhenzhou Liu
* @Date: 2024-07-28
* @Description: 广度优先解题代码
********************************************************************************/
#include <ctype.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#include "tree.h"
#include "uthash.h"

int nearestExit(char** maze, int mazeSize, int* mazeColSize, int* entrance, int entranceSize) {
    int m = mazeSize, n = mazeColSize[0];
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, -1, 0, 1};
    int queue[10000][3], left = 0, right = 0;
    queue[right][0] = entrance[0];
    queue[right][1] = entrance[1];
    queue[right++][2] = 0;
    maze[entrance[0]][entrance[1]] = '+';

    while (left < right) {
        int* point = queue[left++];
        int x = point[0], y = point[1], d = point[2];
        for (int i = 0; i < 4; ++i) {
            int newX = x + dx[i], newY = y + dy[i];
            if (newX >= 0 && newX < m && newY >= 0 && newY < n && (maze[newX][newY] == '.')) {
                if (newX == 0 || newX == m - 1 || newY == 0 || newY == n - 1)
                    return d + 1;

                maze[newX][newY] = '+';
                queue[right][0] = newX;
                queue[right][1] = newY;
                queue[right++][2] = d + 1;

            }
        }
    }
    return -1;
}

int shortestBridge(int** grid, int gridSize, int* gridColSize) {
    int que[10000][2], isLand[10000][2];
    int queFront = 0, queRear = 0, isLandFront = 0, isLandRear = 0;
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, -1, 0, 1};

    for (int i = 0; i < gridSize; ++i) {
        for (int j = 0; j < gridSize; ++j) {
            if (grid[i][j] == 1) {
                que[queRear][0] = i;
                que[queRear++][1] = j;
                grid[i][j] = -1;

                while (queFront < queRear) {
                    int x = que[queFront][0], y = que[queFront++][1];
                    isLand[isLandRear][0] = x;
                    isLand[isLandRear++][1] = y;

                    for (int k = 0; k < 4; ++k) {
                        int newX = x + dx[k], newY = y + dy[k];
                        if (newX >= 0 && newX < gridSize && newY >= 0 && newY < gridSize && grid[newX][newY] == 1) {
                            que[queRear][0] = newX;
                            que[queRear++][1] = newY;
                            grid[newX][newY] = -1;
                        }
                    }
                }

                int step = 0;
                while (isLandFront < isLandRear) {
                    int levelSize = isLandRear - isLandFront;
                    for (int k = 0; k < levelSize; ++k) {
                        int x = isLand[isLandFront][0], y = isLand[isLandFront++][1];
                        for (int l = 0; l < 4; ++l) {
                            int newX = x + dx[l], newY = y + dy[l];
                            if (newX >= 0 && newX < gridSize && newY >= 0 && newY < gridSize) {
                                if (grid[newX][newY] == 1)
                                    return step;
                                else if (grid[newX][newY] == 0) {
                                    isLand[isLandRear][0] = newX;
                                    isLand[isLandRear++][1] = newY;
                                    grid[newX][newY] = -1;
                                }
                            }
                        }
                    }
                    ++step;
                }
            }
        }
    }
    return 0;
}

int minMutation(char * startGene, char * endGene, char ** bank, int bankSize){
    if (!strcmp(startGene, endGene))
        return 0;
    int adj[10][10];
    memset(adj, 0, sizeof(adj));
    int endIndex = -1;
    for (int i = 0; i < bankSize; ++i) {
        if (!strcmp(endGene, bank[i]))
            endIndex = i;
        for (int j = i + 1; j < bankSize; ++j) {
            int diffCount = 0;
            for (int k = 0; k < 8; ++k) {
                if (bank[i][k] != bank[j][k])
                    diffCount++;
                if (diffCount > 1)
                    break;
            }
            if (diffCount == 1) {
                adj[i][j] = 1;
                adj[j][i] = 1;
            }
        }
    }

    if (endIndex == -1)
        return -1;

    int queue[100], front = 0, rear = 0;
    bool visited[10];
    memset(visited, false, sizeof(visited));
    for (int i = 0; i < bankSize; ++i) {
        int diffCount = 0;
        for (int k = 0; k < 8; ++k) {
            if (bank[i][k] != startGene[k])
                diffCount++;
            if (diffCount > 1)
                break;
        }
        if (diffCount == 1) {
            queue[rear++] = i;
            visited[i] = true;
        }
    }

    int step = 1;
    while (front < rear) {
        int levelSize = rear - front;
        for (int i = 0; i < levelSize; ++i) {
            int x = queue[front++];
            if (x == endIndex)
                return step;
            for (int j = 0; j < bankSize; ++j) {
                if (adj[x][j] == 1 && !visited[j]) {
                    queue[rear++] = j;
                    visited[j] = true;
                }
            }
        }
        ++step;
    }
    return -1;
}

struct Trie
{
    int ch[27];
    int val;
}trie[50001];

int size, nodeNum;

void insert(char *word, int num)
{
    int length = strlen(word), add = 0;
    for (int i = 0; i < length; ++i)
    {
        int x = word[i] - '`';
        if (trie[add].ch[x] == 0)
        {
            trie[add].ch[x] = ++size;
            memset(trie[size].ch, 0, sizeof(trie[size].ch));
            trie[size].val = -1;
        }
        add = trie[add].ch[x];
    }
    trie[add].val = num;
}

int search(char *word)
{
    int length = strlen(word), add = 0;
    for (int i = 0; i < length; ++i)
    {
        int x = word[i] - '`';
        if (trie[add].ch[x] == 0)
            return -1;
        add = trie[add].ch[x];
    }
    return trie[add].val;
}

int addWord(char *word)
{
    if (search(word) == -1)
    {
        insert(word, nodeNum++);
    }
    return search(word);
}

int edge[30001][26];
int edgeSize[30001];

void addEdge(char* word)
{
    int length = strlen(word), id1 = addWord(word);
    for (int i = 0;i < length; ++i)
    {
        char tmp = word[i];
        word[i] = '`';
        int id2 = addWord(word);
        edge[id1][edgeSize[id1]++] = id2;
        edge[id2][edgeSize[id2]++] = id1;
        word[i] = tmp;
    }
}


int ladderLength(char* beginWord, char* endWord, char** wordList, int wordListSize) {
    size = nodeNum = 0;
    memset(trie[size].ch, 0, sizeof(trie[size].ch));
    trie[size].val = -1;
    memset(edgeSize, 0, sizeof(edgeSize));

    for (int i = 0; i < wordListSize; ++i)
    {
        addEdge(wordList[i]);
    }
    addEdge(beginWord);
    int beginId = search(beginWord), endId = search(endWord);
    if (endId == -1)
        return 0;

    int disBegin[nodeNum];
    memset(disBegin, -1, sizeof(disBegin));
    disBegin[beginId] = 0;
    int queBegin[nodeNum];
    int leftBegin = 0, rightBegin = 0;
    queBegin[rightBegin++] = beginId;

    int disEnd[nodeNum];
    memset(disEnd, -1, sizeof(disEnd));
    disEnd[endId] = 0;
    int queEnd[nodeNum];
    int leftEnd = 0, rightEnd = 0;
    queEnd[rightEnd++] = endId;


    while (leftBegin < rightBegin && leftEnd < rightEnd)
    {
        int queBeginSize = rightBegin - leftBegin;
        for (int i = 0; i < queBeginSize; ++i)
        {
            int nodeBegin = queBegin[leftBegin++];
            if (disEnd[nodeBegin] != -1)
                return (disBegin[nodeBegin] + disEnd[nodeBegin]) / 2 + 1;
            for (int j = 0; j < edgeSize[nodeBegin]; ++j)
            {
                if (disBegin[edge[nodeBegin][j]] == -1)
                {
                    disBegin[edge[nodeBegin][j]] = disBegin[nodeBegin] + 1;
                    queBegin[rightBegin++] = edge[nodeBegin][j];
                }
            }
        }


        int queEndSize = rightEnd - leftEnd;
        for (int i = 0; i < queEndSize; ++i)
        {
            int nodeEnd = queEnd[leftEnd++];
            if (disBegin[nodeEnd] != -1)
                return (disBegin[nodeEnd] + disEnd[nodeEnd]) / 2 + 1;
            for (int j = 0; j < edgeSize[nodeEnd]; ++j)
            {
                if (disEnd[edge[nodeEnd][j]] == -1)
                {
                    disEnd[edge[nodeEnd][j]] = disEnd[nodeEnd] + 1;
                    queEnd[rightEnd++] = edge[nodeEnd][j];
                }
            }
        }
    }
    return 0;
}


bool canReach(int* arr, int arrSize, int start){
    if (arr[start] == 0)
        return true;

    int left = 0, right = 0;
    int queue[arrSize];
    queue[right++] = start;
    bool visited[arrSize];
    memset(visited, 0, sizeof(visited));
    visited[start] = true;

    while (left < right)
    {
        int cur = queue[left++];
        int tmp = cur + arr[cur];
        if (tmp < arrSize && !visited[tmp])
        {
            if (arr[tmp] == 0)
                return true;
            queue[right++] = tmp;
            visited[tmp] = true;
        }
        tmp = cur - arr[cur];
        if (tmp >=0 && !visited[tmp])
        {
            if (arr[tmp] == 0)
                return true;
            queue[right++] = tmp;
            visited[tmp] = true;
        }
    }
    return false;
}

int** updateMatrix(int** mat, int matSize, int* matColSize, int* returnSize, int** returnColumnSizes) {
    int m = matSize, n = matColSize[0];
    int **dist = (int **) calloc(m, sizeof(int *));
    bool visited[m][n];
    int queue[10000][2], left = 0, right = 0;
    for (int i = 0; i < m; ++i) {
        dist[i] = (int *)malloc(n * sizeof(int));
        for (int j = 0; j < n; ++j) {
            dist[i][j] = 0;
            if (mat[i][j]) {
                visited[i][j] = false;
            } else {
                visited[i][j] = true;
                queue[right][0] = i, queue[right++][1] = j;
            }
        }
    }

    int direction[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
    while (left < right) {
        int x = queue[left][0], y = queue[left++][1];
        for (int i = 0; i < 4; ++i) {
            int newX = x + direction[i][0], newY = y + direction[i][1];
            if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY]) {
                dist[newX][newY] = dist[x][y] + 1;
                queue[right][0] = newX;
                queue[right++][1] = newY;
                visited[newX][newY] = true;
            }
        }
    }
    *returnSize = matSize;
    *returnColumnSizes = matColSize;
    return dist;
}

// 在 C 语言中，二维数组和指向指针的指针在内存布局上是不同的，所以直接传递 grid 会导致未定义行为，从而可能引发段错误。
int shortestPathBinaryMatrix(int** grid, int gridSize, int* gridColSize) {
    if (grid[0][0] == 1)
        return -1;
    int dist[gridSize][gridSize];
    // memset's second param is unsigned char, which is between 0 and 255
    memset(dist, 0x3f, sizeof(dist));
    dist[0][0] = 1;

    int left = 0, right = 0;
    int queue[gridSize * gridSize][2];
    queue[right][0] = 0, queue[right++][1] = 0;
    while (left < right)
    {
        int x = queue[left][0], y = queue[left++][1];
        if (x == gridSize -1 && y == gridSize -1)
            return dist[x][y];
        for (int dx = -1; dx <= 1; ++dx)
        {
            for (int dy = -1; dy <= 1; ++dy)
            {
                int newX = x + dx, newY = y + dy;
                if (newX < 0 || newX >= gridSize || newY < 0 || newY >= gridSize)
                    continue;
                if (grid[newX][newY] == 1 || dist[newX][newY] <= dist[x][y] + 1)
                    continue;
                dist[newX][newY] = dist[x][y] + 1;
                queue[right][0] = newX;
                queue[right++][1] = newY;
            }
        }
    }
    return -1;
}

struct HashTable {
    int key;
    struct TreeNode* val;
    UT_hash_handle hh;
};

void modify(struct HashTable** map, int key, struct HashTablea* node) {
    struct HashTable* it;
    HASH_FIND_INT(*map, &key, it);
    if (it) {
        it->val = node;
    } else {
        it = (struct HashTable *) malloc(sizeof(struct HashTable));
        it->key = key;
        it->val = node;
        HASH_ADD_INT(*map, key, it);
    }
}

struct TreeNode* query(struct HashTable** map, int key) {
    struct HashTable* it;
    HASH_FIND_INT(*map, &key, it);
    if (it) {
        return it->val;
    } else {
        return NULL;
    }
}

struct HashTable* parents;
int* ans;
int ansSize;

void findParents(struct TreeNode* root) {
    if (root->left) {
        modify(&parents, root->left->val, root);
        findParents(root->left);
    }
    if (root->right) {
        modify(&parents, root->right->val, root);
        findParents(root->right);
    }
}

void findAns(struct TreeNode* from, struct TreeNode* node, int depth, int k) {
    if (!node) {
        return;
    }
    if (depth == k) {
        ans[ansSize++] = node->val;
        return;
    }

    if (node->left != from) {
        findAns(node, node->left, depth + 1, k);
    }

    if (node->right != from) {
        findAns(node, node->right, depth + 1, k);
    }

    struct TreeNode* parent = query(&parents, node->val);
    if (parent != from) {
        findAns(node, parent, depth + 1, k);
    }
}

int* distanceK(struct TreeNode* root, struct TreeNode* target, int k, int* returnSize) {
    ans = (int *) calloc(500, sizeof(int));
    // In some case, global variables may not be 0 or NULL.
    ansSize = 0;
    parents = NULL;
    findParents(root);
    findAns(NULL, target, 0, k);
    *returnSize = ansSize;
    return ans;
}

typedef struct {
    int key;
    int value;
    UT_hash_handle hh;
} HashItem;

HashItem* hashFindItem(HashItem** obj, int key)
{
    HashItem* pEntry;
    HASH_FIND_INT(*obj, &key, pEntry);
    return pEntry;
}

bool hashAddItem(HashItem** obj, int key, int value)
{
    if (hashFindItem(obj, key))
        return false;
    HashItem* pEntry = malloc(sizeof(HashItem));
    pEntry->key = key;
    pEntry->value = value;
    HASH_ADD_INT(*obj, key, pEntry);
    return true;
}

bool hashSetItem(HashItem** obj, int key, int value)
{
    HashItem* pEntry = hashFindItem(obj, key);
    if (!pEntry)
        hashAddItem(obj, key, value);
    else
        pEntry->value = value;
    return true;
}

int hashGetItem(HashItem** obj, int key, int defaultValue)
{
    HashItem* pEntry = hashFindItem(obj, key);
    if (!pEntry)
        return defaultValue;
    return pEntry->value;
}

void hashFree(HashItem** obj)
{
    HashItem *curr = NULL, *tmp = NULL;
    HASH_ITER(hh, *obj, curr, tmp)
    {
        HASH_DEL(*obj, curr);
        free(curr);
    }
}

typedef struct
{
    int x;
    int y;
    int mask;
} Tuple;

Tuple *createTuple(int x, int y, int mask)
{
    Tuple* obj = malloc(sizeof(Tuple));
    obj->x = x;
    obj->y = y;
    obj->mask = mask;
    return obj;
}

int shortestPathAllKeys(char** grid, int gridSize) {
    int directions[][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
    int m = gridSize, n = strlen(grid[0]);
    int sx = 0, sy = 0;
    HashItem *key_to_idx = NULL;



    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            char ch = grid[i][j];
            if (ch == '@')
            {
                sx = i;
                sy = j;
            } else if (islower(ch))
            {
                if (!hashFindItem(&key_to_idx, ch))
                {
                    int idx = HASH_COUNT(key_to_idx);
                    hashAddItem(&key_to_idx, ch, idx);
                }
            }
        }
    }


    int keySize = HASH_COUNT(key_to_idx);
    int dist[m][n][1 << keySize];
    // 只有设置-1时，int类型数据4个数据都为-1，整体也为-1
    memset(dist, -1, sizeof(dist));
    dist[sx][sy][0] = 0;
    Tuple* queue[m * n * (1 << keySize)];
    int head = 0, tail = 0;
    queue[tail++] = createTuple(sx, sy, 0);
    while (head != tail)
    {
        Tuple* tmp = queue[head];
        int x = tmp->x, y = tmp->y, mask = tmp->mask;
        free(tmp);
        ++head;
        for (int i = 0; i < 4; ++i)
        {
            int nx = x + directions[i][0], ny = y + directions[i][1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] != '#')
            {
                char ch = grid[nx][ny];
                if (ch == '.' || ch == '@')
                {
                    if (dist[nx][ny][mask] == -1)
                    {
                        dist[nx][ny][mask] = dist[x][y][mask] + 1;
                        queue[tail++] = createTuple(nx, ny, mask);
                    }
                } else if (islower(ch))
                {
                    int idx = hashGetItem(&key_to_idx, ch, -1);
                    int new_mask = mask | 1 << idx;
                    if (dist[nx][ny][new_mask] == -1)
                    {
                        dist[nx][ny][new_mask] = dist[x][y][mask] + 1;
                        if (new_mask == (1 << keySize) - 1)
                        {
                            hashFree(&key_to_idx);
                            return dist[nx][ny][new_mask];
                        }
                        queue[tail++] = createTuple(nx, ny, new_mask);
                    }
                } else
                {
                    int idx = hashGetItem(&key_to_idx, tolower(ch), -1);
                    int key = mask & (1 << idx);
                    if (key && dist[nx][ny][mask] == -1)
                    {
                        dist[nx][ny][mask] = dist[x][y][mask] + 1;
                        queue[tail++] = createTuple(nx, ny, mask);
                    }
                }
            }
        }
    }
    hashFree(&key_to_idx);
    return -1;
}


int main() {
    char temp[][5] = {"@.a..", "###.#", "b.A.B"};
    char *grid[3];
    grid[0] = temp[0];
    grid[1] = temp[1];
    grid[2] = temp[2];
    printf("%d", shortestPathAllKeys(grid, 3));
    return 0;
}